package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode216 
* @author      : ganwei 
* @date        : 2020年5月11日 
* @Description : Leetcode216 组合总和 III 
*/
public class Leetcode0216 {
	List<List<Integer>> result = new ArrayList<>();
    /**
     * -回溯大法，必须搞懂
     */
	public List<List<Integer>> combinationSum3(int k, int n) {
    	backtrack(k,n,1,0,new ArrayList<Integer>());
		return result;
    }
	/**
	 * -回溯主体
	 */
	public void backtrack(int k, int n, int index, int sum, List<Integer> il) {
		if(il.size() == k) {
			if(n == sum) {
				result.add(new ArrayList<Integer>(il));
			}
			return;
		}
		
		for(int i = index; i <= 9; i++) {
			if(sum + i > n) {
				continue;
			}
			il.add(i);
			backtrack(k,n,i+1,sum+i,il);
			il.remove(il.size()-1);
		}
	}
	
	public static void main(String[] args) {
		Leetcode0216 l216 = new Leetcode0216();
		l216.combinationSum3(2, 18);
		for(List<Integer> l : l216.result) {
			for(Integer ii : l) {
				System.out.print(ii);
				System.out.print(" ");
			}
			System.out.println();
		}
	}
    
    
}
